package vip.zhenzicheng.demo.app;

import lombok.ToString;

import java.util.Collection;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * 手写HashMap，只实现最基础的概念与大体流程
 *
 * @author zhenzicheng
 * @date 2022-10-15 09:16
 * @see java.util.HashMap
 */
@ToString
public class ThirdHashMap<K, V> implements Map<K, V> {

  // 默认容量
  static final int DEFAULT_CAPACITY = 16;

  // 负载因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  /**
   * hash冲突链表深度达到8准备转红黑树
   */
  static final int TREEIFY_THRESHOLD = 8;

  /**
   * 防止频繁的与红黑树互转浪费性能，所以hash冲突链表小于该值才会转回链表
   */
  static final int UNTREEIFY_THRESHOLD = 6;

  /**
   * 准备转红黑树还需要判断当前hash桶总长度大于该值，否则只是扩容
   */
  static final int MIN_TREEIFY_CAPACITY = 64;

  // HashMap大小
  transient int size;

  // 桶数组
  transient Node<K, V>[] buckets;


  public ThirdHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
  }

  public ThirdHashMap(int capacity) {
    // TODO check capacity
    buckets = new Node[capacity];
  }

  private int getIndex(K key, int length) {
    int hashCode = key.hashCode();
    // 计算下标
    int index = hashCode % length;
    return Math.abs(index);
  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean containsKey(Object key) {
    // 下标
    int index = getIndex((K) key, this.buckets.length);
    if (this.buckets != null) {
      Node<K, V> node = this.buckets[index];
      // 遍历下标节点所在链表
      while (node != null) {
        if ((node.key.hashCode() == key.hashCode()) &&
          (node.key == key || node.key.equals(key))) {
          return true;
        }
        node = node.next;
      }
    }
    return false;
  }

  @Override
  public boolean containsValue(Object value) {
    // 只能遍历所有元素来找了
    if (this.buckets != null) {
      for (Node<K, V> bucket : this.buckets) {
        while (bucket != null) {
          if (Objects.equals(value, bucket.value)) {
            return true;
          }
          bucket = bucket.next;
        }
      }
    }
    return false;
  }

  @Override
  public V get(Object key) {
    // 下标
    int index = getIndex((K) key, this.buckets.length);
    if (this.buckets[index] == null) {
      return null;
    }
    Node<K, V> node = this.buckets[index];
    // 查找链表
    while (node != null) {
      if ((node.key.hashCode() == key.hashCode()) &&
        (node.key == key || node.key.equals(key))) {
        return node.value;
      }
      node = node.next;
    }
    return null;
  }

  @Override
  public V put(K key, V value) {
    // 判断是否需要扩容
    if (this.size >= buckets.length * DEFAULT_LOAD_FACTOR) {
      resize(); // 不考虑红黑树
    }
    Node<K, V>[] table = this.buckets;
    return putVal(key, value, table);
  }

  // TODO null k,v 没有处理
  private V putVal(K key, V value, Node<K, V>[] table) {
    // 获取下标
    int index = getIndex(key, table.length);
    Node<K, V> node = table[index];
    // 为空直接新建Node节点
    if (node == null) {
      table[index] = new Node<>(key, value);
      this.size++;
      return value;
    }
    // 不为空说明发生hash冲突，遍历链表
    while (node != null) {
      // 发生hash冲突并且元素还相同，则应该覆盖
      if ((node.key.hashCode() == key.hashCode())
        && (node.key == key || node.key.equals(key))) {
        node.value = value; // 覆盖
        return value;
      }
      node = node.next; // 下推链表
    }
    // 当前key不在链表中，已经遍历到链表尾
    Node<K, V> oldHead = table[index];
    Node<K, V> newNode = new Node<>(key, value, table[index]);
    table[index] = newNode;
    newNode.next = oldHead;
    // TODO jdk1.7使用头插，可能在多线程扩容出现环形链表，jdk1.8使用尾插，保证原链表顺序
    this.size++;
    return value;
  }

  /**
   * HashMap扩容固定为2的整数倍
   */
  private void resize() {
    Node<K, V>[] newBuckets = new Node[this.buckets.length * 2];
    // 重新散列当前元素
    rehash(newBuckets);
    this.buckets = newBuckets;
  }

  private void rehash(Node<K, V>[] newBuckets) {
    this.size = 0; // 重新计算Map大小
    for (int i = 0; i < buckets.length; i++) {
      if (buckets[i] == null) {
        continue;
      }
      Node<K, V> node = buckets[i];
      // 把每个node节点对应的链表数据都转移到新位置
      while (node != null) {
        putVal(node.key, node.value, newBuckets);
        node = node.next;
      }
    }
  }

  @Override
  public V remove(Object key) {
    return null;
  }

  @Override
  public void putAll(Map<? extends K, ? extends V> m) {

  }

  @Override
  public void clear() {
    Node<K, V>[] tab;
    if ((tab = this.buckets) != null && size > 0) {
      size = 0;
      // 将数组每个节点都置null
      for (int i = 0; i < tab.length; ++i)
        tab[i] = null;
    }
  }

  @Override
  public Set<K> keySet() {
    return null;
  }

  @Override
  public Collection<V> values() {
    return null;
  }

  @Override
  public Set<Entry<K, V>> entrySet() {
    return null;
  }


  static class Node<K, V> {
    private K key;
    private V value;

    private Node<K, V> next;

    public Node(K key, V value) {
      this.key = key;
      this.value = value;
    }

    public Node(K key, V value, Node<K, V> next) {
      this.key = key;
      this.value = value;
      this.next = next;
    }
  }

  public static void main(String[] args) {
    Map<String, String> map = new ThirdHashMap<>(2);
    map.put("zzc", "甄老师");
    map.put("lc", "刘经理");
    map.put("xlc", "续工");
    System.out.println(map.size());
    System.out.println(map.containsKey("zzc"));
    System.out.println(map.get("lc"));
    System.out.println(map);
  }
}
